package src.dp.sequence;

public class no115 {//不同的子序列

    /**
     * dp[i][j]含义：以i-1结尾的s中，有 以j-1结尾的t 的个数是dp[i][j]
     * 递推公式：分两种情况：
     * 1、s[i-1] 与 t[j-1]相等，dp[i][j]有两部分组成
     * 一部分是用s[i-1]来匹配，那么个数为dp[i-1][j-1]，一部分是不用s[i-1]来匹配，个数为dp[i-1][j]
     * 2、s[i-1] 与 t[j-1]不相等，dp[i][j]只有一部分组成，不用s[i-1]来匹配，个数为dp[i-1][j]
     * 初始化数组：dp[0][0] = 0, dp[i][0] = 1, dp[0][j] = 0
     * 遍历顺序：数组从左往右，从上往下
     */
    public int numDistinct(String s, String t) {
        int len1 = s.length(), len2 = t.length();
        int[][] dp = new int[len1 + 1][len2 + 1];

        dp[0][0] = 1;
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; j <= len2; j++) {
            dp[0][j] = 0;
        }

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    //i遍历s，j遍历t，i-1即i前移一位，j不动
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[len1][len2];

    }
}
